#include <stdlib.h>
#include <stdio.h>
#include "mpi.h"
#include "tokenize.h"
#include "userinput.h"

#define IOTAG 1
#define SERVERTAG 3

#define IORANK 0
#define SERVERRANK 1

unsigned long long hard_vector[64];
int vector_size;

int collisions;
unsigned long long * possibilities;
int p_size;
int numprocs, rank;
int server_server_rank;
int server_numprocs;

FILE *vptr;
FILE *cptr;

MPI_Comm server_comm;

inline unsigned long long * getArray(int numULL)
{
	return (unsigned long long *)malloc(sizeof(unsigned long long) * numULL);
}

//adds a possibility for the current token to the array of possibilities
//if adding would overflow the array then double the size of the array
//copy over, free the old array and set the old arrays pointer to the new
//array
void addPossibility(unsigned long long poss)
{
	if(collisions + 1 > p_size)
	{
		unsigned long long * ptr = getArray(p_size * 2);
		int i;
		for(i=0; i < p_size; i++)
		{
			ptr[i] = possibilities[i];
		}
		free(possibilities);
		possibilities = ptr;
		p_size *= 2;
	}
	
	possibilities[collisions] = poss;
	collisions++;
}

//prints out the number chars from a possibility bit string
//the bits will be in an unsigned long long so we need to take
//them out 8 at a time
void printChars(int index)
{
	//since we are constraining the size of the vector to multiples
	//of 8 we cand do this division
	int numChars = vector_size / 8;
	int i;
	unsigned long long poss = possibilities[index];
	
	for(i = 0; i < numChars; i++)
	{
	//(numChars - i - 1) * 8 is how many bits right the unsigned long long
	//needs to be shifted to put the current character into the bottom 8 bits
		printf("%c", (poss >> ((numChars - i - 1) * 8)) & 0xFF);
	}
}

//new printing code
void printLong(unsigned long long num)
{
	int i;
	int mask = 0xFF;
	
	for(i=vector_size-8; i>=0; i-=8)
	{
		printf("%c", (char)((num >> i) & mask));
	}
}

void printPossibility()
{
	int j;

	if(collisions > 1)
	{
		printf("[ ");
		for(j=0; j < collisions; j ++)
		{
			unsigned long long poss = possibilities[j];
			printLong(poss);
			if(j == collisions -1)
			{
				printf(" ");
			}
			else
			{
				printf(", ");
			}
		}
		printf("]");
	}
	else if (collisions == 1)
	{
		printLong(possibilities[0]);
	}
}
//runs the IO Node
//this consists of parsing a token from the cipher text, sending it to the
//server node, parsing another token, and then waiting to send to the server
//returns when there exists no more tokens in cipher text
void runIONode()
{
	unsigned long long token;
	while ((token = getNextToken(cptr)) != 0)
	{
	   MPI_Send(&token, 1, MPI_UNSIGNED_LONG_LONG, SERVERRANK, IOTAG,
		MPI_COMM_WORLD);
	}
	// token guaranteed to be 0
	MPI_Send(&token, 1, MPI_UNSIGNED_LONG_LONG, SERVERRANK, IOTAG,
	   MPI_COMM_WORLD);

	fclose(cptr);
}

/*
Server node does the following:
1. Receives a cipher token from the IO node
2. Sends this token to all the compute nodes
3. Receives all possibilities for a token's decryption
 3a. Waits to receive a "message" from a compute node
 3b. if the message is a 0, that compute node is done with its part of the
	computation.  Otherwise, that number is a possible decrypted char
 3c. when all compute nodes return 0, computation is complete for this token
4. Print out the possibilities for this token
5. Repeat steps 1-4 until a token containing 0 is received
*/
void runServerNode()
{
	int i;
	unsigned long long token;
	possibilities = getArray(10);
	p_size = 10;
	collisions = 0;
	MPI_Request req;

	MPI_Status status;

	//recv token from IO Node
	MPI_Recv(&token, 1, MPI_UNSIGNED_LONG_LONG, IORANK, IOTAG,
	   MPI_COMM_WORLD, &status);

	// Send out the cipher token to all compute nodes
	for (i = 0; i < server_numprocs; i++)
	{
	   if (i != server_server_rank)
	   {
	   	MPI_Send(&token, 1, MPI_UNSIGNED_LONG_LONG, i, SERVERTAG,
		   server_comm);
	   }

	}
	
	while (token != 0)
	{
	   int done = 0;
	   while (done < server_numprocs-1)
	   {
			unsigned long long message;
			//recv either a zero or a possibility from a compute node
			MPI_Recv(&message, 1, MPI_UNSIGNED_LONG_LONG, MPI_ANY_SOURCE,
				MPI_ANY_TAG, server_comm, &status);
	
			if (message == 0)
				done++;
			else
				addPossibility(message);
		}
		
		// Receive next token from IO node
		MPI_Recv(&token, 1, MPI_UNSIGNED_LONG_LONG, IORANK, IOTAG,
		MPI_COMM_WORLD, &status);

		// Send out the cipher token to all compute nodes
		for (i = 0; i < server_numprocs; i++)
		{
			if (i != server_server_rank)
			{
				
				MPI_Isend(&token, 1, MPI_UNSIGNED_LONG_LONG, i, SERVERTAG,
					server_comm, &req);
			}
	   }
		printPossibility();
		collisions = 0;	   		
	}
}

//Compute nodes find the actual solution to the knapsack cipher problem by
//looking at every possible solution as deemed by the solving algorithm
void runComputeNode()
{
	unsigned long long i,j,sum,token;
	unsigned long long loops = 1 << vector_size;
	
	MPI_Status status;

	//receive token (the first time)
	MPI_Recv(&token, 1, MPI_UNSIGNED_LONG_LONG, server_server_rank,
	   SERVERTAG, server_comm, &status);
	
	while (token != 0)
	{
	   //for (i = start; i < end; i++)
	   for(i = rank -2; i < loops; i+= numprocs - 2, sum = 0)
	   {
	   	for (j = 0; j < vector_size; j++)
	   	{
		   if ((1 << j) & i)
		   	sum += hard_vector[vector_size - j - 1];
	   	}

	   	if (token == sum)
	   	{
		   MPI_Isend(&i, 1, MPI_UNSIGNED_LONG_LONG, server_server_rank,
		   	SERVERTAG, server_comm,&req);
	   	}
	   }

	   // Signals to server that it is done with this token
	   i = 0;
	   MPI_Send(&i, 1, MPI_UNSIGNED_LONG_LONG, server_server_rank,
		SERVERTAG, server_comm);

	   // Receives next token (might be 0)
	   MPI_Recv(&token, 1, MPI_UNSIGNED_LONG_LONG, server_server_rank,
		SERVERTAG, server_comm, &status);
		
	}
}

int main(int argc, char *argv[])
{

	unsigned long long vec_value;
	unsigned long long token;
	int i,j;
	int ioranks[] = {IORANK};

	MPI_Init(&argc,&argv);

	MPI_Comm_size(MPI_COMM_WORLD, &numprocs);
	MPI_Comm_rank(MPI_COMM_WORLD, &rank);

	MPI_Group world_group, server_group;
	MPI_Comm_group(MPI_COMM_WORLD, &world_group);
	MPI_Group_excl(world_group, 1, ioranks, &server_group);
	MPI_Comm_create(MPI_COMM_WORLD, server_group, &server_comm);

	MPI_Group_free(&world_group);
	MPI_Group_free(&server_group);

	// Begin timing
	double startTime = MPI_Wtime();

	// Lets all non-IO nodes know size of server_comm
	if (rank != IORANK)
	   MPI_Comm_size(server_comm, &server_numprocs);

	// IO Node needs cipher text
	if (rank == IORANK)
	   cptr = fopen("cipher.txt","r");
	
	MPI_Barrier(MPI_COMM_WORLD);

	// Server Node needs hard vector
	if (rank == SERVERRANK)
	{
	   //vptr = (FILE *)getVectorFileFromUser();
	   vptr = fopen("hvec.txt","r");

	   //initialize the hard_vector
	   for(i = 0; i < 64, (vec_value = getNextToken(vptr)) != 0; i++)
	   {
		hard_vector[i] = vec_value;
		vector_size++;
	   }

	   // Gets rank of the server in the server_comm
	   MPI_Comm_rank(server_comm, &server_server_rank);
	   fclose(vptr);
	}
	
	// Broadcasts vector size for a later broadcast
	MPI_Bcast(&vector_size, 1, MPI_INT, SERVERRANK, MPI_COMM_WORLD);

	// Broadcasts the server's rank in the server_comm
	MPI_Bcast(&server_server_rank, 1, MPI_INT, 1, MPI_COMM_WORLD);

	// Broadcasts the values in the hard vector
	MPI_Bcast(hard_vector, vector_size, MPI_UNSIGNED_LONG_LONG,
		SERVERRANK, MPI_COMM_WORLD);


	// Initiates all duties
	if (rank == IORANK) runIONode();
	else if (rank == SERVERRANK) runServerNode();
	else runComputeNode();

	MPI_Barrier(MPI_COMM_WORLD);

	if (rank == 0)
	{
	   double endTime = MPI_Wtime();
	   printf("\nTotal time: %lf\n", endTime - startTime);
	}
	MPI_Finalize();
	return 0;
}

